#include <util.h>
#include <qsort.h>
#include <rand_select.h>

int rand_select_tst(int argc, char *argv[])
{
    int i, n, r;
    int *a;

    if (argc < 3)
    {
        printf("usage: %s n i\n", argv[0]);
        return -1;    
    }
    n = strtol(argv[1], NULL, 10);
    if (n <= 0)
        n = 10;
    i = strtol(argv[2], NULL, 10);
    if (i <= 0)
        i = 1;

    if ((a = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }
    srand(time(NULL));

    for (r = 0; r < n; r++)
    {
        a[r] = r+1;
    }
    // randomize in place
    /*
    for (r = 0; r < n; r++)
    {
        swap(&a[r], &a[r+rand()%(n-r)]);//a[r] = (rand() % rand()) % (rand() % time(NULL));
    }
    */
    permute_in_place(a, sizeof(a[0]), 0, n-1);

    print_a(a, n, NULL);

#if 0
    printf("%dth smallest element is %d\n", i, rand_select(a, 0, n-1, i));
#else
    printf("%dth smallest element is %d\n", i, rand_select_nr(a, 0, n-1, i));
#endif

    quicksort(a, 0, n-1);
    print_a(a, n, NULL);

    if (a)
        free(a);

    return 0;
}

int 
select_min_max_tst(int argc, char *argv[])
{
    int n, r, min, max;
    int *a;

    if (argc < 2)
    {
        printf("usage: %s n\n", argv[0]);
        return -1;    
    }
    n = strtol(argv[1], NULL, 10);
    if (n <= 0)
    {
        printf("size %d defaults to 10\n", n);
        n = 10;
    }

    if ((a = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }

    for (r = 0; r < n; r++)
    {
        a[r] = r+1;
    }
    permute_in_place(a, sizeof(a[0]), 0, n-1);
    print_a(a, n, NULL);

    select_min_max(a, 0, n-1, &min, &max);

    printf("min %d, max %d\n", min, max);

    quicksort(a, 0, n-1);
    print_a(a, n, NULL);

    if (a)
        free(a);

    return 0;
}

//#define _RAND_SEL_TST_
//#define _MIN_MAX_SEL_TST_

int main(int argc, char *argv[])
{
#if defined(_RAND_SEL_TST_)
    rand_select_tst(argc, argv);
#endif

#if defined(_MIN_MAX_SEL_TST_)
    select_min_max_tst(argc, argv);
#endif

    //rand_select_median_tst(argc, argv);
    // rand_select_by_median_tst(argc, argv);
    two_array_median_tst(argc, argv);

    exit(0);
}

int 
rand_select_median_tst(int argc, char *argv[])
{
    int n, r;
    int *a;

    if (argc < 2)
    {
        printf("usage: %s n\n", argv[0]);
        return -1;    
    }
    n = strtol(argv[1], NULL, 10);
    if (n <= 0)
        n = 10;

    if ((a = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }
    srand(time(NULL));

    for (r = 0; r < n; r++)
    {
        a[r] = r+1;
    }
    // randomize in place
    /*
    for (r = 0; r < n; r++)
    {
        swap(&a[r], &a[r+rand()%(n-r)]);//a[r] = (rand() % rand()) % (rand() % time(NULL));
    }
    */
    permute_in_place(a, sizeof(a[0]), 0, n-1);

    print_a(a, n, NULL);

    printf("median is %d\n", rand_select_median(a, 0, n-1));

    quicksort(a, 0, n-1);
    print_a(a, n, NULL);

    if (a)
        free(a);

    return 0;
}

int 
rand_select_by_median_tst(int argc, char *argv[])
{
    int n, r, i;
    int *a;

    if (argc < 3)
    {
        printf("usage: %s n i\n", argv[0]);
        return -1;    
    }
    n = strtol(argv[1], NULL, 10);
    if (n <= 0)
        n = 10;
    i = strtol(argv[2], NULL, 10);
    if (i <= 0)
        i = 1;

    if ((a = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }
    srand(time(NULL));

    for (r = 0; r < n; r++)
    {
        a[r] = r+1;
    }
    // randomize in place
    permute_in_place(a, sizeof(a[0]), 0, n-1);

    print_a(a, n, NULL);

    printf("%dth order staistic is %d\n", i, rand_select_by_median(a, 0, n-1, i));

    quicksort(a, 0, n-1);
    print_a(a, n, NULL);

    if (a)
        free(a);

    return 0;
}

int 
two_array_median_tst(int argc, char *argv[])
{
    int n, i, should;
    int *x, *y, *z;

    if (argc < 2)
    {
        printf("usage: %s n\n", argv[0]);
        return -1;    
    }
    n = strtol(argv[1], NULL, 10);
    if (n <= 0)
        n = 10;

    if ((x = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }
    if ((y = (int *)malloc(sizeof(int) * n)) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }
    if ((z = (int *)malloc(sizeof(int) * (2*n))) == NULL)
    {
        fprintf(stderr, "malloc(3) error\n");
        return -1;
    }

    srand(time(NULL));

    /*
    for (i = 0; i < n; i++)
    {
        if (rand() % 2)
        {
            x[i] = 2 * i;
            y[i] = 2 * i + 1;
        }
        else
        {
            x[i] = 2 * i + 1;
            y[i] = 2 * i;
        }
        z[2*i] = x[i];
        z[2*i+1] = y[i];
    }
    */
    // get 2n distinct numbers
L_RETRY:
    for (i = 0; i < 2 * n; i++)
    {
        srand(rand() % 7351 + time(NULL) / (i+1));
        z[i] = rand() % 1031;
    }
    quicksort(z, 0, 2*n-1);
    if (not_uniq(z, 2 * n))
        goto L_RETRY;
    should = z[n-1];
    print_a(z, 2*n, NULL);

    // permute to distribute to x[] and y[] randomly
    permute_in_place(z, sizeof(int), 0, 2*n-1);
    memcpy(x, z, sizeof(int) * n);
    memcpy(y, z+n, sizeof(int) * n);
    quicksort(x, 0, n-1);
    quicksort(y, 0, n-1);
    print_a(x, n, NULL);
    print_a(y, n, NULL);

    printf("median %d, should be %d\n", two_ordered_array_median(x, y, n), should);

    if (x)
        free(x);
    if (y)
        free(y);
    if (z)
        free(z);

    return 0;
}

